<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>2526：[Poi2011]Inspection</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Poi2011]Inspection</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Poi2011]Inspection</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Poi2011]Inspection                </h1>
                <p>时间限制：35s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p></p>
<p></p>
<div style="line-height: 140%"><span style="font-size: medium"><span style="color: #444444; line-height: 140%">The railway network of the Byteotian Railways (BR) consists of bidirectional tracks connecting certain pairs of stations. Each pair of stations is connected by at most one segment of tracks. Furthermore, there is a unique route from every station to every other station. (The route may consist of several segments of tracks, but it may not pass through any station more than once.) </span></span></div>
<div style="line-height: 140%"><span style="font-size: medium"><span style="color: #444444; line-height: 140%">Byteasar is an undercover inspector of the BR. His job is to pick one of the stations (denote it by S) for centre of his operations and to travel to all other stations. His journey should be as follows: </span></span></div>
<div style="margin: 0cm 0cm 0pt 191.25pt; text-indent: -18pt; line-height: 140%"><span style="font-size: medium"><span style="color: #444444; line-height: 140%">&middot;<span style="font: 7pt 'Times New Roman'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>Byteasar starts in station S. </span></span></div>
<div style="margin: 0cm 0cm 0pt 191.25pt; text-indent: -18pt; line-height: 140%"><span style="font-size: medium"><span style="color: #444444; line-height: 140%">&middot;<span style="font: 7pt 'Times New Roman'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>Next, he picks one of the stations he did not yet control and goes to it along the shortest path (by train, of course), inspects the station, and then goes back to S. </span></span></div>
<div style="margin: 0cm 0cm 0pt 191.25pt; text-indent: -18pt; line-height: 140%"><span style="font-size: medium"><span style="color: #444444; line-height: 140%">&middot;<span style="font: 7pt 'Times New Roman'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>The crooked employees of BR warn one another of Byteasar's comings. To deceive them, Byteasar picks the next station for control in such a way that he sets off from the station Sin different direction than the last time, i.e., along a different segment of tracks leaving from S. </span></span></div>
<div style="margin: 0cm 0cm 0pt 191.25pt; text-indent: -18pt; line-height: 140%"><span style="font-size: medium"><span style="color: #444444; line-height: 140%">&middot;<span style="font: 7pt 'Times New Roman'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>Each station (except S) is inspected exactly once. </span></span></div>
<div style="margin: 0cm 0cm 0pt 191.25pt; text-indent: -18pt; line-height: 140%"><span style="font-size: medium"><span style="color: #444444; line-height: 140%">&middot;<span style="font: 7pt 'Times New Roman'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>After inspecting the last station Byteasar <b>does not come back</b> to S. </span></span></div>
<div style="line-height: 140%"><span style="font-size: medium"><span style="color: #444444; line-height: 140%">The travel time along every segment of tracks takes the same amount of time: one hour. </span></span></div>
<div style="line-height: 140%"><span style="font-size: medium"><span style="color: #444444; line-height: 140%">Byteasar intends to consider all the stations as the initial station S. For each of them he wants to know the order of inspecting the remaining stations that minimises the total travel time, provided that it is possible at all for that particular S. </span></span></div>
<div style="line-height: 140%"></div>
<div style="line-height: 140%"><span style="font-size: medium">Byteasar是Byteoian Railways的一名便衣巡视员。BR的铁路架构是一棵N个节点的树，Byteasar需要检查所有的N个节点。他按照如下方式行动：</span></div>
<p></p>
<pre style="font-family: arial, verdana, helvetica, sans-serif! important"><span style="font-size: medium">首先选定一个行动中心S，并且检查S。
从S出发前往任意一个未检查的点（沿树上两点的唯一最短路走），检查该节点，然后返回S。
特别地，检查完最后一个节点后不需要返回。
检查节点不需要时间，走过一条路的时间为1。
为了不暴露身份，Byteasar规定相邻两次检查所经过的道路不允许有重复。
也就是说，除第一次检查之外，他每次从S出发走过的第一条边不能和上一次出发相同。
输入：
第一行是一个整数N。(1&lt;=n&lt;=1000000)
接下来N-1行每行有2个整数A,B，表示A和B之间有一条边。
输出：&nbsp;</span></pre>
<p></p>
<div style="line-height: 140%"></div>
<p><span style="font-size: medium">N行，第I行表示如果以I作为行动中心，Byteasar检查完所有车站需要的最小时间。如果不可能做到，该行输出-1。<br />
</span></p></p><hr/><h3>输入格式</h3><p><div style="line-height: 140%"><span style="font-size: medium"><span style="color: #444444; line-height: 140%">The first line of the standard input contains a single integer N(1&lt;=N&lt;=1000000) that denotes the number of stations. These are numbered from 1 to n . The following &nbsp;n -1 lines specify the track segments, one per line. Each of them holds two integers a,b(1&lt;=A,B&lt;=N,A&lt;&gt;B), separated by a single space, indicating that there is a track segment connecting the stations &nbsp;a and b. Each track segments appears exactly once in the description. </span></span></div>
<div style="line-height: 140%"><span style="font-size: medium"><span style="color: #444444; line-height: 140%">In tests worth at least 30% of the points it holds additionally that n&lt;=2000. </span></span></div></p><hr/><h3>输出格式</h3><p><div style="line-height: 140%"><span style="font-size: medium"><span style="color: #444444; line-height: 140%">Your program should print lines on the standard output, each holding a single integer. The one in the i-th line should be the minimum number of hours Byteasar has to spend travelling to inspect the stations when s=i- if inspecting them all is possible for s=i; if it is not, the i-th line should hold the number -1. </span></span></div></p><hr/><h3>样例输入</h3><pre>9
3 6
2 4
2 6
2 5
1 7
2 7
8 9
7 8
</pre><hr/><h3>样例输出</h3><pre>-1
23
-1
-1
-1
-1
-1
-1
-1</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>鸣谢 Object022</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=2526" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=2526" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>